The problem of assigning random pairings between data elements subject to a set of restrictions occurs in many areas. The pairings may be between elements of the same data set, in which each element of the data set is paired with another element from the same set, or between elements from different data sets in which each element from a first data set is assigned to an element of a second data set.
An example of an assignment problem between elements from different data sets is the assignment of a set of people to a set of tasks. Some people are restricted from performing specific tasks, so the assignment is restricted. For example, a person may be unable or unqualified to perform a particular task.
An example of pairings between elements of the same data set is a “Secret Santa” gift exchange, in which each person in a workgroup is assigned to give a gift to another (randomly selected) member of the workgroup. There may be restrictions to the assignment. For example, a person may not be permitted to buy a gift for a direct supervisor or receive a gift from a direct subordinate. A restriction is used to designate a specified pairing of gift giver and gift receiver as prohibited.
The assignment may be made manually, whereby a person randomly assigns pairs and then makes changes as needed in an attempt to avoid prohibited pairings.
Alternatively, all of the possible pairings can be examined, and the finally set of pairings can be chosen at random from among those pairings that meet all of the restrictions.
However, as the number of data elements becomes large, both of these methods fail. For example, in a group of 15 elements (a 15 member workgroup for example) there are billions of possible pairings. If, in addition, there are many restrictions, a manual search is unlikely to find a set of pairings that meets all of the restrictions. An exhaustive search, even by a fast computer will also take a prohibitively long time, even with as few as 10-15 entries.